package demo1;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //K次取反后最大化的数组和
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int sum = 0;
        if(nums[n-1]<0 && k>n){
            for(int each:nums) sum+=each;
            if((k-n)%2==0) return -sum;
            else return -(sum-nums[n-1]*2);
        }
        for (int i = 0; i < n && k>0; i++,k--) {
            if(nums[i]<0){
                nums[i] = -nums[i];
            }else if(nums[i]>=0 && k%2==0){
                k=0;
            }else if(nums[i]>=0 && k%2==1){
                Arrays.sort(nums);
                nums[0] = -nums[0];
            }
        }

        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        return sum;
    }

    //最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int ret = 1;
        int max = Integer.MIN_VALUE;
        for(int i = 1;i < n; i++){
            if(nums[i]>nums[i-1]) ++ret;
            else {
                max = Math.max(max,ret);
                ret = 1;
            }
        }
        return Math.max(ret,max);
    }

    //递增的三元子序列
    public boolean increasingTriplet(int[] nums) {
        int a = nums[0];
        int b = Integer.MAX_VALUE;
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>b) return true;
            else if(nums[i]>a) b = nums[i];
            else if(nums[i]<a) a = nums[i];
        }
        return false;
    }

    public boolean increasingTriplet1(int[] nums) {
        ArrayList<Integer> ret = new ArrayList<>();
        int n = nums.length;
        ret.add(nums[0]);
        for(int i = 1;i<n;i++){
            if(nums[i]>ret.get(ret.size()-1)){
                ret.add(nums[i]);
            }else{
                int left = 0;
                int right = ret.size()-1;
                while(left<right){
                    int mid = left+(right-left)/2;
                    if(nums[i]>ret.get(left)) left = mid+1;
                    else right = mid;
                }
                ret.set(left,nums[i]);
            }
            if(ret.size()>=3) return true;
        }
        return false;
    }

    //最长递增子序列（贪心）
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(nums[0]);
        for (int i = 1; i < n; i++) {
            if(nums[i]>ret.get(ret.size()-1)){
                ret.add(nums[i]);
            }else {
                int left = 0;
                int right = ret.size()-1;
                while (left < right) {
                    int mid = left+(right-left)/2;
                    if(ret.get(mid)<nums[i]) left = mid+1;
                    else right = mid;
                }
                ret.set(left,nums[i]);
            }
        }
        return ret.size();
    }

    public static void main1(String[] args) {
        int[] arr = {1,3,5,6};
        test(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void test(int[] arr){
        arr[0] = 2;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,3,2,3};
        //lengthOfLIS(nums);
    }

    //最长递增子序列
    public static int lengthOfLIS1(int[] nums) {
        int[] retArray = new int[nums.length];
        int size = 1;
        for (int i = 0; i < nums.length; i++) {
            int ret = swap(retArray,nums[i],size);
            size = ret>size?ret:size;
        }
        return size-1;
    }

    private static int swap(int[] arr,int key,int size){
        int left = 0;
        int right = size-1;
        while(left<right){
            int mid = left + (right-left+1)/2;
            if(key>arr[mid]){
                left = mid;
            }else if(key<=arr[mid]){
                right = mid-1;
            }
        }
        if(key>arr[left]) arr[left+1] = key;
        else arr[left] = key;
        return key>arr[left]?size+1:size;
    }
}
